n = int(input())
for i in range(n):
(a, b) = map(int, input().split(' '))
if max(a, b) % min(a, b) == 0:
print(max(a, b) // min(a, b))
else:
operations = 0
bigger_number = max(a, b)
smaller_number = min(a, b)
while bigger_number != smaller_number:
if bigger_number < smaller_number:
smaller_number, bigger_number = bigger_number, smaller_number
if bigger_number % smaller_number == 0:
operations += (bigger_number - smaller_number) // smaller_number
break
else:
operations += bigger_number // smaller_number
bigger_number = bigger_number % smaller_number
print(operations + 1)
#include <cstdio>
int main(){
int n; scanf("%d", &n);
while(n--){
long a(0), b(0); scanf("%ld %ld", &a, &b);
long total(0);
while(a > 0 && b > 0){
if(a > b){total += a/b; a -= (a/b) * b;}
else{total += b/a; b -= (b/a) * a;}
}
printf("%ld\n", total);
}
return 0;
}1669D - Colorful Stamp | 1669B - Triple |
1669A - Division | 1669H - Maximal AND |
1669E - 2-Letter Strings | 483A - Counterexample |
3C - Tic-tac-toe | 1669F - Eating Candies |
1323B - Count Subrectangles | 991C - Candies |
1463A - Dungeon | 1671D - Insert a Progression |
1671A - String Building | 1671B - Consecutive Points Segment |
1671C - Dolce Vita | 1669G - Fall Down |
4D - Mysterious Present | 1316B - String Modification |
1204A - BowWow and the Timetable | 508B - Anton and currency you all know |
1672A - Log Chopping | 300A - Array |
48D - Permutations | 677C - Vanya and Label |
1583B - Omkar and Heavenly Tree | 1703C - Cypher |
1511C - Yet Another Card Deck | 1698A - XOR Mixup |
1702E - Split Into Two Sets | 1703B - ICPC Balloons |